# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def flipMatchVoyage(self, root: TreeNode, voyage: list) -> list:
        res = []
        stack = []
        if root:
            stack.append(root)
        i = 0
        while stack:
            node = stack.pop()
            if node.val != voyage[i]:
                res = [-1]
                break
            if node.left is None and node.right is None:
                i += 1
                continue
            if node.left and node.right:
                if node.left.val != voyage[i + 1]:
                    if node.right.val == voyage[i + 1]:
                        temp = node.left
                        node.left = node.right
                        node.right = temp
                        res.append(node.val)
                    else:
                        res = [-1]
                        break
            elif node.left:
                if node.left.val != voyage[i + 1]:
                    res = [-1]
                    break
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            i += 1

        return res


if __name__ == "__main__":
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node1.left = node2
    node1.right = node3

    print(Solution().flipMatchVoyage(node1, [1, 3, 2]))
